/**
 * @url https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
 * @author dingyue.zhf
 * @description 449. 序列化和反序列化二叉搜索树
 */

/**
 *
 * 助教
 * 1. 序列化时，助教的分隔符只有一种，按照中序遍历将搜索二叉树通过分隔符分隔开即可
 * 2. 反序列化时，先排序然后生成搜索二叉树，存储的内容为数字
 *
 * 船长
 * 1. 序列化的分隔符更加复杂，包含,()
 * 2. 反序列化通过状态机生成
 *
 *
 * 不使用分隔符
 * 1. 使用位运算用4个字节表示整数
 *
 *
 * 搜索二叉树的性质
 * 1. 左边节点都比自己小
 * 2. 右边节点都比自己大
 *
 *
 * 官方
 * 1. 通过后序遍历序列化
 *
 *
 *
 * 1. 二叉搜索树只能通过前序和后序构造
 * 2. 首末节点是确定的 123456789
 * 3. 为什么要取最后一个节点作为根节点，万一取错了怎么办
 */

// 方案一 后序遍历+递归
/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  /** 后序遍历 */
  const postOrder = (node) => {
    // 处理极限情况
    if (!node) {
      return [];
    }
    const left = node.left ? postOrder(node.left) : [];
    const right = node.right ? postOrder(node.right) : [];
    return left.concat(right, node.val);
  };

  const arr = postOrder(root);

  return arr.join(' ');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  //! 处理极限情况
  if (!data) {
    return null;
  }
  const arr = data.split(' ');
  // bst 表示二叉搜索树，简称b-tree
  /** 递归生成节点 */
  const bst = (min, max) => {
    if (!arr.length) {
      return null;
    }
    const str = arr.pop();
    const val = parseInt(str);
    if (val < min || val > max) {
      arr.push(str);
      return null;
    }
    return {
      val,
      // 这里的顺序很重要，因为后续遍历是左右根，所以应该倒车
      right: bst(val, max),
      left: bst(min, val),
    };
  };
  return bst(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
};
